//题目：
// 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
// 请你将两个数相加，并以相同形式返回一个表示和的链表。
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头
#include<iostream>

using namespace std;
//代码:
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* lit1, ListNode* lit2) {
        //法一：
        // if(lit1==nullptr)return lit2;
        // if(lit2==nullptr)return lit1;

        // int carry=0;//进位标识符
        // ListNode* cur_1=lit1,*cur_2=lit2,*cur;

        // int result=cur_1->val+cur_2->val+carry;
        // if(result>=10) carry=result/10;
        // else carry=0;
        // ListNode* head=new ListNode(result%10);//新链表的头结点

        // cur_1=cur_1->next,cur_2=cur_2->next,cur=head;

        // while(cur_1 && cur_2)
        // {
        //     result=cur_1->val+cur_2->val+carry;//计算
        //     if(result>=10)
        //         carry=result/10;
        //     else 
        //         carry=0;
        //     ListNode* newnode=new ListNode(result%10);
        //     cur->next=newnode,cur=newnode;//对新链表进行尾插
        //     cur_1=cur_1->next,cur_2=cur_2->next;//更新
        // }
        // //当某一链表的值被用完后，要加上剩余那个链表的值
        // while(cur_1)
        // {
        //     result=cur_1->val+carry;
        //     if(result>=10)
        //         carry=result/10;
        //     else 
        //         carry=0;
        //     ListNode* newnode=new ListNode(result%10);
        //     cur->next=newnode,cur=newnode;
        //     cur_1=cur_1->next;
        // }
        // while(cur_2)
        // {
        //     result=cur_2->val+carry;
        //     if(result>=10)
        //         carry=result/10;
        //     else 
        //         carry=0;
        //     ListNode* newnode=new ListNode(result%10);
        //     cur->next=newnode,cur=newnode;
        //     cur_2=cur_2->next;
        // }
        // if(carry)cur->next=new ListNode(carry);
        // return head;
        //法二（升级版）:
        ListNode* cur1=lit1,*cur2=lit2;
        ListNode* virtual_head=new ListNode(0);//引入一个虚拟头结点
        ListNode* cur=virtual_head;
        int carry=0;//进位标识
        while(cur1 || cur2 || carry){
            if(cur1) carry+=cur1->val,cur1=cur1->next;
            if(cur2) carry+=cur2->val,cur2=cur2->next;
            cur->next=new ListNode(carry%10);//保留个位
            cur=cur->next;
            carry/=10;//更新进位标识
        }
        cur=virtual_head->next;
        delete virtual_head;
        return cur;
    }
};